package Main2;

import javax.swing.text.html.CSS;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.Stack;

//复习笔试强训7-9天
public class Main789 {
    //合法括号判断
    public boolean chkParenthesis(String A, int n) {
        if (n % 2 != 0) return false;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < A.length(); i++) {
            char ch = A.charAt(i);
            if (ch == '(') {
                stack.push(ch);
            }else if (ch == ')') {
                if (stack.isEmpty()) return false;
                else stack.pop();
            }else {
                return false;
            }
        }
        return stack.isEmpty();
    }
    //Fibonacci数列
    public static void main2(String[] args) {
       Scanner scan = new Scanner(System.in);
       while (scan.hasNext()) {
           int num = scan.nextInt();
           int f1 = 0;
           int f2 = 1;
           while (f2 < num) {
               int f3 = f1 + f2;
               f1 = f2;
               f2 = f3;
           }
           //走到这里斐波那契数要么比num小,要么比num大
           int right = f2;
           int left = f1;
           int a = right - num;
           int b = num - left;
           System.out.println(Math.min(a, b));
       }
    }

    //最小公倍数
    public static void main1(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            if (a < b) {
                int tmp = a;
                a = b;
                b = tmp;
            }
            for (int i = a; i > 0; i++) {
                if (a % i == 0 && b % i == 0) {
                    System.out.println(i);
                    break;
                }
            }
        }
    }
    //最小公倍数思路2
    public static void main3(String[] args) {
        //最小公倍数 = a*b / a和b的最大公约数
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = a*b / gdc(a, b);
        System.out.println(c);
    }

    private static int gdc(int a, int b) {
        if (a == b) return a;
        if (a < b) {
            int tmp = a;
            a = b;
            b = tmp;
        }
        int c;
        while ((c = a % b) > 0) {
            a = b;
            b = c;
        }
        return b;
    }
    //两种排序方法
    public static void main4(String[] args) throws IOException {
        //BufferReader从字符流中读取文本并缓存
        BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bi.readLine());
        String[] strs = new String[n];
        for (int i = 0; i < n; i++) {
            strs[i]= bi.readLine();
        }
        //判断
    }

    public static void main5(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int n = scan.nextInt();
            String[] str = new String[n];
            for (int i = 0; i < n; i++) {
                str[i] = scan.next();
            }
            boolean len = isLenSort(str);
            boolean dic = isDicSort(str);
            if (len && dic) System.out.println("both");
            else if (len) System.out.println("lengths");
            else if (dic) System.out.println("lexicographically");
            else System.out.println("none");
        }
    }

    private static boolean isDicSort(String[] str) {
        for (int i = 0; i < str.length - 1; i++) {
            if (str[i].compareTo(str[i+1]) > 0) return false;
        }
        return true;
    }

    private static boolean isLenSort(String[] str) {
        for (int i = 0; i < str.length - 1; i++) {
            if (str[i].length() > str[i+1].length()) {
                return false;
            }
        }
        return true;
    }
    //另类加法
    /*结论: 如果两个数相加,二进制位不需要进位,结果就是二进制位相亦或的结果
    * 如果两个数相加,二进制位需要进位,此时就需要两个数的二进制位按位与后左移一位
    * 一直循环这个过程,一直到两个数相加二进制位不需要进位*/
    public int addAB(int A, int B) {
        if (B == 0) return A;
        int sum = 0;
        int carry = 0;
        while (B != 0) {
            sum = A ^ B;
            carry = (A & B) << 1;
            A = sum;
            B = carry;
        }
        return A;
    }
    //求路径总数
    //对于求路径总数简单的问题可以用递归求解,复杂的问题就用动态规划的方式求解
    public static void main6(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int n = scan.nextInt();//行数
            int m = scan.nextInt();//列数
            System.out.println(med(n , m));
        }
    }

    private static int med(int n, int m) {
        if (n == 1 && m >= 1 || m == 1 && n >= 1) {
            return n + m;
        }
        return med(n-1, m) + med(n, m-1);
    }
    //求路径总数: 动态规划求解
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int n = scan.nextInt();
            int m = scan.nextInt();
            // n 和 m表示的就是节点的个数 如果是2行2列的方格就有9个节点
            int[][] dp = new int[n + 1][m + 1];
            for (int i = 0; i <= n; i++) {
                for (int j = 0; j <= m; j++) {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    }else {
                        dp[i][j] = dp[i-1][j] + dp[i][j-1];
                    }
                }
            }
            System.out.println(dp[n][m]);
        }
    }

}
